package com.lims.algorithm.algset.heap;

import java.util.ArrayList;
import java.util.List;

/**
 * <功能简述>最小堆
 *
 * @author lims
 * @date 2020-07-21 19:19
 */
public class MinHeap<T extends Comparable<T>> {
    List<T> mHeap;

    public MinHeap() {
        mHeap = new ArrayList<>();
    }

    /**
     * 插入最小堆
     *
     * @param data
     */
    public void insert(T data) {
        int size = mHeap.size();

        mHeap.add(data);
        fixUp(size, data);
    }

    /**
     * 最小堆向上调整算法
     *
     * @param start 准备向上调整的结点索引下标
     * @param data  准备向上调整的结点数据
     */
    protected void fixUp(int start, T data) {
        // 追踪指针c
        int c = start;
        // c的父结点指针
        int p;
        // 结点比较标记
        int cmp;
        while (c > 0) {
            p = (c - 1) / 2;
            cmp = data.compareTo(mHeap.get(p));
            if (cmp < 0) {
                // 用父结点替代当前结点，相当于父结点下移，父结点原位置空出
                mHeap.set(c, mHeap.get(p));
                // 当前指针cl指向p，开始向上调整
                c = p;
            } else {
                break;
            }
        }
        mHeap.set(c, data);
    }

    /**
     * 删除结点
     *
     * @param data
     */
    public int remove(T data) {
        if (mHeap.isEmpty()) {
            return -1;
        }
        int index = mHeap.indexOf(data);
        if (index == -1) {
            return -1;
        }
        int size = mHeap.size();
        T tmp = mHeap.get(size - 1);
        mHeap.set(index, tmp);
        mHeap.remove(size - 1);
        if (mHeap.size() > 1) {
            fixDown(index, mHeap.size() - 1);
        }
        return 0;
    }

    /**
     * 最小堆向下调整算法
     *
     * @param start
     * @param end
     */
    protected void fixDown(int start, int end) {
        int c = start;
        int l = 2 * c + 1;
        T tmp = mHeap.get(c);
        while (l <= end) {
            int cmp;
            // 边界 c只有左子l，没有右子l+1
            if (l + 1 <= end) {
                cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
                // 选择左右孩子较小的
                if (l < end && cmp > 0) {
                    l++;
                }
            }
            cmp = tmp.compareTo(mHeap.get(l));
            if (cmp <= 0) {
                break;
            } else {
                mHeap.set(c, mHeap.get(l));
                c = l;
                l = 2 * c + 1;
            }
        }
        mHeap.set(c, tmp);
    }

    @Override
    public String toString() {
        return mHeap.toString();
    }

    /********************************************************/
    public static void main(String[] args) {
        MinHeap<Integer> minHeap = new MinHeap<>();
        /*int a[] = {80, 40, 30, 60, 90, 70, 10, 50, 20};

        System.out.println("== 依次添加： ");
        for (int i : a) {
            System.out.printf("%d ", i);
            minHeap.insert(i);
        }

        System.out.printf("\n ==最小堆: %s", minHeap);

        minHeap.remove(10);
        System.out.printf("\n ==最小堆: %s", minHeap);*/

        minHeap.insert(4);
        minHeap.insert(5);
        minHeap.insert(8);

        System.out.printf("\n ==最小堆: %s", minHeap);

        minHeap.remove(4);

        System.out.printf("\n ==最小堆: %s", minHeap);
    }
}
